using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0238. 除自身以外数组的乘积")]
    public class No0238_ProductExceptSelf : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(ProductExceptSelf2, new int[] { 1, 2, 3, 4 }, new int[] { 24, 12, 8, 6 });
            Assert.TestExe(ProductExceptSelf2, new int[] { 0, 2, 3, 4 }, new int[] { 24, 0, 0, 0 });
        }

        /// <summary>
        /// 方法一: 左右乘积列表
        /// 时间复杂度: O(N)
        /// 空间复杂度: O(N)
        /// </summary>
        public int[] ProductExceptSelf(int[] nums)
        {
            int len = nums.Length;

            // L 和 R 分别表示左右两侧的乘积列表

            // L[i] 为索引 i 左侧所有元素的乘积
            // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
            int[] L = new int[len];
            L[0] = 1;
            for (int i = 1; i < L.Length; i++)
            {
                L[i] = L[i - 1] * nums[i - 1];
            }

            // R[i] 为索引 i 右侧所有元素的乘积
            // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
            int[] R = new int[len];
            R[len - 1] = 1;
            for (int i = len - 2; i >= 0; i--)
            {
                R[i] = R[i + 1] * nums[i + 1];
            }

            // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
            int[] answer = new int[len];
            for (int i = 0; i < len; i++)
            {
                answer[i] = L[i] * R[i];
            }
            return answer;
        }

        /// <summary>
        /// 进阶:
        /// 时间复杂度: O(N)
        /// 空间复杂度: O(1)
        /// </summary>
        public int[] ProductExceptSelf2(int[] nums)
        {
            int len = nums.Length;

            // answer[i] 表示索引 i 左侧所有元素的乘积
            // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
            int[] answer = new int[len];
            answer[0] = 1;
            for (int i = 1; i < answer.Length; i++)
            {
                answer[i] = answer[i - 1] * nums[i - 1];
            }

            // R 为右侧所有元素的乘积
            // 刚开始右边没有元素，所以 R = 1
            int R = 1;
            for (int i = len - 1; i >= 0; i--)
            {
                // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
                answer[i] = answer[i] * R;

                // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
                R = R * nums[i];
            }
            return answer;
        }
    }
}
